home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / map.h < prev    next >
C/C++ Source or Header  |  1997-06-22  |  9KB  |  250 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  * Copyright (c) 1997
  27.  * Moscow Center for SPARC Technology
  28.  *
  29.  * Permission to use, copy, modify, distribute and sell this software
  30.  * and its documentation for any purpose is hereby granted without fee,
  31.  * provided that the above copyright notice appear in all copies and
  32.  * that both that copyright notice and this permission notice appear
  33.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  34.  * representations about the suitability of this software for any
  35.  * purpose.  It is provided "as is" without express or implied warranty.
  36.  *
  37.  */
  38.  
  39. #ifndef __SGI_STL_MAP_H
  40. # define __SGI_STL_MAP_H
  41.  
  42. # ifndef __SGI_STL_TREE_H
  43. #  include <tree.h>
  44. # endif
  45.  
  46. __BEGIN_STL_NAMESPACE
  47. __BEGIN_STL_FULL_NAMESPACE
  48. #define map __WORKAROUND_RENAME(map)
  49.  
  50. template <class Key, class T, __DFL_TMPL_PARAM(Compare,less<Key>), 
  51.                               __DFL_TYPE_PARAM(Alloc,alloc) >
  52. class map {
  53.     typedef map<Key, T, Compare, Alloc> self;
  54. public:
  55.  
  56. // typedefs:
  57.  
  58.   typedef Key key_type;
  59.   typedef T data_type;
  60.   typedef pair<const Key, T> value_type;
  61.   typedef Compare key_compare;
  62.     
  63.   class value_compare
  64.         : public binary_function<value_type, value_type, bool> {
  65.     friend class map<Key, T, Compare, Alloc>;
  66.     protected :
  67.         Compare comp;
  68.         value_compare(Compare c) : comp(c) {}
  69.     public:
  70.         bool operator()(const value_type& x, const value_type& y) const {
  71.             return comp(x.first, y.first);
  72.         }
  73.   };
  74.  
  75. private:
  76.   typedef rb_tree<key_type, value_type, 
  77.                   select1st<value_type, value_type::first_type>, key_compare, Alloc> rep_type;
  78. public:
  79.   typedef typename rep_type::reference reference;
  80.   typedef typename rep_type::const_reference const_reference;
  81.   typedef typename rep_type::iterator iterator;
  82.   typedef typename rep_type::const_iterator const_iterator;
  83.   typedef typename rep_type::reverse_iterator reverse_iterator;
  84.   typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
  85.   typedef typename rep_type::size_type size_type;
  86.   typedef typename rep_type::difference_type difference_type;
  87.  
  88. private:
  89.   rep_type t;  // red-black tree representing map
  90.  
  91.   // allocation/deallocation
  92. public:
  93.   map() : t(Compare()) {}
  94.   explicit map(const Compare& comp) : t(comp) {}
  95.   map(const value_type* first, const value_type* last) : 
  96.       t(Compare()) {
  97.         t.insert_unique(first, last);
  98.   }
  99.   map(const value_type* first, const value_type* last, 
  100.       const Compare& comp) : t(comp) {
  101.         t.insert_unique(first, last);
  102.   }
  103.   map(const_iterator first, const_iterator last) : 
  104.       t(Compare()) {
  105.         t.insert_unique(first, last);
  106.   }
  107.   map(const_iterator first, const_iterator last, 
  108.       const Compare& comp) : t(comp) {
  109.         t.insert_unique(first, last);
  110.   }
  111.   map(const map<Key, T, Compare, Alloc>& x) : t(x.t) {}
  112.   map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x)
  113.   {
  114.     t = x.t;
  115.     return *this; 
  116.   }
  117.  
  118.   // accessors:
  119.  
  120.   key_compare key_comp() const { return t.key_comp(); }
  121.   value_compare value_comp() const { return value_compare(t.key_comp()); }
  122.   iterator begin() { return t.begin(); }
  123.   const_iterator begin() const { return t.begin(); }
  124.   iterator end() { return t.end(); }
  125.   const_iterator end() const { return t.end(); }
  126.   reverse_iterator rbegin() { return t.rbegin(); }
  127.   const_reverse_iterator rbegin() const { return t.rbegin(); }
  128.   reverse_iterator rend() { return t.rend(); }
  129.   const_reverse_iterator rend() const { return t.rend(); }
  130.   bool empty() const { return t.empty(); }
  131.   size_type size() const { return t.size(); }
  132.   size_type max_size() const { return t.max_size(); }
  133.   T& operator[](const key_type& k) {
  134.     return (*((insert(value_type(k, T()))).first)).second;
  135.   }
  136.   void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }
  137.  
  138.   // insert/erase
  139.  
  140.   pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
  141.   iterator insert(iterator position, const value_type& x) {
  142.     return t.insert_unique(position, x);
  143.   }
  144.   void insert(const value_type* first, const value_type* last) {
  145.     t.insert_unique(first, last);
  146.   }
  147.   void insert(const_iterator first, const_iterator last) {
  148.     t.insert_unique(first, last);
  149.   }
  150.   void erase(iterator position) { t.erase(position); }
  151.   size_type erase(const key_type& x) { return t.erase(x); }
  152.   void erase(iterator first, iterator last) { t.erase(first, last); }
  153.   void clear() { t.clear(); }
  154.  
  155.   // map operations:
  156.  
  157.   iterator find(const key_type& x) { return t.find(x); }
  158.   const_iterator find(const key_type& x) const { return t.find(x); }
  159.   size_type count(const key_type& x) const { return t.count(x); }
  160.   iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
  161.   const_iterator lower_bound(const key_type& x) const {
  162.     return t.lower_bound(x); 
  163.   }
  164.   iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
  165.   const_iterator upper_bound(const key_type& x) const {
  166.     return t.upper_bound(x); 
  167.   }
  168.   
  169.   pair<iterator,iterator> equal_range(const key_type& x) {
  170.     return t.equal_range(x);
  171.   }
  172.   pair<const_iterator,const_iterator> equal_range(const key_type& x) const {
  173.     return t.equal_range(x);
  174.   }
  175.   friend bool operator==(const self&, const self&);
  176.   friend bool operator<(const self&, const self&);
  177. // debug
  178.     bool __rb_verify() const { return t.__rb_verify(); } 
  179. };
  180.  
  181.  
  182. __END_STL_FULL_NAMESPACE
  183.  
  184. // do a cleanup
  185. # undef map
  186. # define __map__  __FULL_NAME(map)
  187.  
  188. template <class Key, class T, class Compare, class Alloc>
  189. inline bool operator==(const __map__<Key, T, Compare, Alloc>& x, 
  190.                        const __map__<Key, T, Compare, Alloc>& y) {
  191.   return x.t == y.t;
  192. }
  193.  
  194. template <class Key, class T, class Compare, class Alloc>
  195. inline bool operator<(const __map__<Key, T, Compare, Alloc>& x, 
  196.                       const __map__<Key, T, Compare, Alloc>& y) {
  197.   return x.t < y.t;
  198. }
  199.  
  200. # if defined (__STL_CLASS_PARTIAL_SPECIALIZATION )
  201. template <class Key, class T, class Compare, class Alloc>
  202. inline void swap(__map__<Key, T, Compare, Alloc>& a,
  203.                  __map__<Key, T, Compare, Alloc>& b) { a.swap(b); }
  204. # endif
  205.  
  206. // provide a way to access full funclionality 
  207. # ifndef __STL_DEFAULT_TYPE_PARAM
  208. // provide a "default" map adaptor
  209. template <class Key, class T, class Compare>
  210. class map : public __map__<Key, T, Compare, alloc>
  211. {
  212.     typedef map<Key, T, Compare> self;
  213. public:
  214.     typedef __map__<Key, T, Compare, alloc> super;
  215.     __CONTAINER_SUPER_TYPEDEFS
  216.     __IMPORT_SUPER_COPY_ASSIGNMENT(map)
  217.     map() : super(Compare()) {}
  218.     explicit map(const Compare& comp) : super(comp) {}
  219.     map(const typename super::value_type* first, const typename super::value_type* last) : 
  220.         super(first, last, Compare()) { }
  221.     map(const typename super::value_type* first, const typename super::value_type* last, 
  222.         const Compare& comp) : super(first, last, comp) { }
  223.     map(typename super::const_iterator first, typename super::const_iterator last) : 
  224.         super(first, last, Compare()) { }
  225.     map(typename super::const_iterator first, typename super::const_iterator last, 
  226.         const Compare& comp) : super(first, last, comp) { }
  227. };
  228.  
  229. #  if defined (__STL_BASE_MATCH_BUG)
  230. template <class Key, class T, class Compare>
  231. inline bool operator==(const map<Key, T, Compare>& x, 
  232.                        const map<Key, T, Compare>& y) {
  233.   typedef typename map<Key, T, Compare>::super super;
  234.   return operator==((const super&)x,(const super&)y);
  235. }
  236.  
  237. template <class Key, class T, class Compare>
  238. inline bool operator<(const map<Key, T, Compare>& x, 
  239.                       const map<Key, T, Compare>& y) {
  240.   typedef typename map<Key, T, Compare>::super super;
  241.   return operator < ((const super&)x,(const super&)y);
  242. }
  243. #  endif
  244.  
  245. # endif /*  __STL_DEFAULT_TEMPLATE_PARAM */
  246.  
  247. __END_STL_NAMESPACE
  248.  
  249. #endif
  250.